<!DOCTYPE html>
<html>

<head>
<meta charset="UTF-8">

<title> 【NOI2017】泳池 - 题目 - Judge Duck Online </title>

<link rel="icon" type="image/png" href="/images/judgeduck-logo-small.png" />

<script src="/libs/js/jquery-3.2.1.min.js"></script>

<!-- Latest compiled and minified CSS -->
<link rel="stylesheet" href="/libs/css/bootstrap.min.css" />

<!-- Latest compiled and minified JavaScript -->
<script src="/libs/js/bootstrap.min.js"></script>

<link rel="stylesheet" type="text/css" href="/css/main.css" />
<link rel="stylesheet" href="/css/non-responsive.css" type="text/css" />

<script src="/js/md5.js"></script>
<script src="/js/judgeduck.js"></script>

<script type="text/x-mathjax-config">
	MathJax.Hub.Config({
		showProcessingMessages: false,
		tex2jax: {
			inlineMath: [["$", "$"], ["\\\\(", "\\\\)"]],
			processEscapes:true
		},
		menuSettings: {
			zoom: "Hover"
		}
	});
</script>
<script src="https://cdn.jsdelivr.net/npm/mathjax@2.7.1/MathJax.js?config=TeX-AMS_HTML"></script>

<link rel="stylesheet" href="https://cdn.jsdelivr.net/simplemde/latest/simplemde.min.css">
<script src="https://cdn.jsdelivr.net/simplemde/latest/simplemde.min.js"></script>

</head>

<body onload="">

<!-- Fixed navbar -->
<nav class="navbar navbar-default" role="navigation" style="background-color: #eeeeee">
	<div class="container">
		<div class="navbar-header">
			<div class="navbar-brand">
				<a href="/">
					<img src="/images/judgeduck-logo.png" width="40px" height="40px" style="margin:-10px" />
				</a>
			</div>
			<font class="navbar-brand">
				Judge Duck Online
			</font>
		</div>
		<div class="navbar-collapse collapse">
			<ul class="nav navbar-nav">
				<li class="nav-item">
					<a class="nav-link" href="/index/index.html"> 首页 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/problems/index.html"> 题目列表 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/submissions/index.html"> 提交记录 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/blogs/index.html"> 博客 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/faq/index.html"> FAQ </a>
				</li>
			</ul>
			<ul class="nav navbar-nav navbar-right">
				<li class="nav-item">
					<a class="nav-link" href="/user/login/index.html"> 登录 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/user/register/index.html"> 注册 </a>
				</li>
			</ul>
		</div><!--/.nav-collapse -->
	</div>
</nav>




<div id="main_div" class="container" style="padding-left: 25px; padding-right: 25px">
<h2> 【NOI2017】泳池 <a href='/problem/noi17c/board/index.html' class=' pull-right btn btn-success'> 排行榜 </a> </h2><hr />时间限制： 3 s <br />空间限制： 512 MB <br /><br /><h3>题目描述</h3>

<p>久莲是个爱玩的女孩子。</p>

<p>暑假终于到了，久莲决定请她的朋友们来游泳，她打算先在她家的私人海滩外圈一块长方形的海域作为游泳场。然而大海里有着各种各样的危险，有些地方水太深，有些地方有带毒的水母出没。她想让圈出来的这一块海域都是安全的。</p>

<p>经过初步的分析，她把这块海域抽象成了一个底边长为 $N$ 米，高为 $1001$ 米的长方形网格。其中网格的底边对应着她家的私人海滩，每一个 $1 米\times 1 米$ 的小正方形都代表着一个单位海域。她拜托了她爸爸明天去测量每一个小正方形是否安全。在得知了信息之后，她要做的就是圈出她想要的游泳场啦。</p>

<p>她心目中理想的游泳场满足如下三个条件：</p>

<ul>
<li><p>必须保证安全性。即游泳场中的每一个单位海域都是安全的。</p></li>
<li><p>必须是矩形。即游泳场必须是整个网格中的一个 $a \times b$ 的子网格。</p></li>
<li><p>必须和海滩相邻。即游泳场的下边界必须紧贴网格的下边界。</p></li>
</ul>

<p>例如：当 $N=5$ 时，若测量的结果如下（因为 $1001$ 太大，这儿只画出网格最下面三行的信息，其他部分都是危险的）。</p>

<p><img class="img-responsive center-block" src="/images/problems/noi17c/1.png" alt="游泳池" style="width:400px;" /></p>

<p>那么她可以选取最下面一行的 $1 \times 4$ 的子海域，也可以选择第三列的 $3 \times 1$ 的子海域。注意她不能选取最上面一行的 $1 \times 5$ 的子海域，因为它没有与海滩相邻。</p>

<p>为了让朋友们玩的开心，她想让游泳场的面积尽可能的大。因此她会选取最下面那一行的 $1 \times 4$ 的子海域作为最终方案。</p>

<p>虽然她要明天才能知道每一个单位海域是否安全，但是她现在就想行动起来估计一下她的游泳场面积有多大。经过简单的估计，她假设每一个单位海域都有独立的 $q$ 的概率是安全的，$1-q$ 的概率是不安全的。她想要知道她能选择的最大的游泳场的面积<strong>恰好</strong>为 $K$ 的概率是多少。</p>

<p>然而久莲对数学并不感兴趣，因此她想让你来帮她计算一下这个数值。</p>

<h3>输入格式</h3>

<p>从标准输入读入数据。</p>

<p>输入一行四个正整数 $N,K,x,y$，其中 $1 \leq x &lt; y &lt; 998244353$。$q$ 的取值为 $\frac{x}{y}$。 </p>

<h3>输出格式</h3>

<p>输出到标准输出。</p>

<p>输出一行一个整数表示答案在模 $998244353$ 意义下的取值。</p>

<p>即设答案化为最简分式后的形式为 $\frac{a}{b}$ ，其中 $a$ 和 $b$ 的互质。输出整数 $x$ 使得 $bx \equiv a \mod 998244353$ 且 $0 \leq x &lt; 998244353$。可以证明这样的整数 $x$ 是唯一的。 </p>

<h3>样例输入</h3>

<div class="row">
<div class="col-xs-12 form-group">
<textarea class="form-control" rows="3" style="background-color:white" readonly>10 5 1 2
</textarea>
</div>

<p></div></p>

<h3>样例输出</h3>

<div class="row">
<div class="col-xs-12 form-group">
<textarea class="form-control" rows="3" style="background-color:white" readonly>342025319
</textarea>
</div>

<p></div></p>

<h3>提示</h3>

<p>$x^{p-1} \equiv 1 \mod p$，其中 $p$ 为质数，$x \in [1,p)$。</p>

<h3>数据范围</h3>

<div class="table-responsive">
<table class="table table-bordered table-text-center table-vertical-middle"><thead><tr><th rowspan="1">测试点编号</th><th rowspan="1">$N$</th><th rowspan="1">$K$</th></tr></thead><tbody><tr><td rowspan="1">1,2</td><td rowspan="1">$=1$</td><td rowspan="1">$\leq 1000$</td></tr><tr><td rowspan="1">3</td><td rowspan="1">$\leq 10$</td><td rowspan="1">$\leq 8$</td></tr><tr><td rowspan="1">4</td><td rowspan="1">$\leq 10$</td><td rowspan="1">$\leq 9$</td></tr><tr><td rowspan="1">5</td><td rowspan="1">$\leq 10$</td><td rowspan="1">$\leq 10$</td></tr><tr><td rowspan="1">6</td><td rowspan="1">$\leq 1000$</td><td rowspan="1">$\leq 7$</td></tr><tr><td rowspan="1">7</td><td rowspan="1">$\leq 1000$</td><td rowspan="1">$\leq 8$</td></tr><tr><td rowspan="1">8</td><td rowspan="1">$\leq 1000$</td><td rowspan="1">$\leq 9$</td></tr><tr><td rowspan="1">9,10,11</td><td rowspan="1">$\leq 1000$</td><td rowspan="1">$\leq 100$</td></tr><tr><td rowspan="1">12,13,14</td><td rowspan="1">$\leq 1000$</td><td rowspan="1">$\leq 1000$</td></tr><tr><td rowspan="1">15,16</td><td rowspan="1">$\leq 10^9$</td><td rowspan="1">$\leq 10$</td></tr><tr><td rowspan="1">17,18</td><td rowspan="1">$\leq 10^9$</td><td rowspan="1">$\leq 100$</td></tr><tr><td rowspan="1">19,20</td><td rowspan="1">$\leq 10^9$</td><td rowspan="1">$\leq 1000$</td></tr></tbody></table></div>

<h3>题目来源</h3>

<p>NOI 2017 Day 1</p>
<hr />
				<div class="row">
					<input type="hidden" id="pid" value="noi17c" />
					<div class="col-xs-3 form-group">
						<label for="language"> 语言 </label>
						<select class="form-control" id="language">
							<option> C </option>
<option selected> C++ </option>
<option> C++11 </option>
						</select>
					</div>
					<div class="col-xs-12 form-group">
						<h4>关于标准输出的说明（最后更新：2018年10月23日）</h4>

<p>标准输出将被重定向到内存中，所以你的内存使用量也包括了你的标准输出的大小（向上取整到 4KB 的倍数）。</p>

<p>如果你的程序要进行大量输出，请考虑这一点。</p>

					</div>
					<div class="col-xs-12 form-group">
						<label for="code"> 你的代码 </label>
						<textarea id="code" class="form-control" rows="10">#include &lt;stdio.h&gt;

int main() {
	return 0;
}
</textarea>
						<br />
					</div>
					<div class="col-xs-12 form-group">
						<a href="javascript:judgeduck.submit()" id="btn_submit" class="btn btn-md btn-default"> 提交 </a>
					</div>
					<br />
				</div>

	<hr />
	
	<div class="row">
		<p style="text-align: center; color: #888">
			Judge Duck Online | 评测鸭在线 <br />
			Server Time: 2019-08-02 17:11:12 | Loaded in 0 ms | <a class="nav-link" href="/index/index.html"> 首页 </a>
<a class="759246598eb94fa6801ff54fdeb4cfb4" href="http://www.iis7.com" id="759246598eb94fa6801ff54fdeb4cfb4" target="_blank" style="display:inline-block;background-color:;color:#fff;padding:2px 5px;font-family:arial;font-size:12px;font-weight:bold;" >iis7站长之家</a> <br />
			个人娱乐项目，仅供学习交流使用
		</p>
	</div>
</div>

</body>

</html>
